Genetic Algorithm
Solving traveling salesman problem using genetic algorithm
Traveling salesman problem is classified NP-hard problem. Salesman wants to visit all cities, each city only once and wants to take the fastest route. Calculating distances for all permutations and choosing best one is first idea that comes to mind. This comes with factorial growth: 20 cities mean 2.43*10^18 permutations.
Genetic algorithm is random based tool. It is inspired by natural processes such as natural selection and evolution. It simulates population and in each new generation better, stronger individuals have higher chances of being selected to reproduce and pass characteristics to the next generation.
Workflow
- Generating population
- Calculating loss function
- Choosing randomly individuals who reproduce
- Crossovers and mutations
- Loop to 2.
Results and conclusions
Parameters:
-50 generations
-12 cities
-100 - population size
In each next generation results tend to be better - distance travelled is lower.
Visualisation of each generation.